package com.mlh.skill;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author 缪林辉
 * @date 2024/7/2 11:51
 * @DESCRIPTION
 */
//给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
// 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
public class 多数元素 {
    public int method1(int[] nums) {
        HashMap<Integer,Integer>map=new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(map.containsKey(nums[i])){
                map.put(nums[i],map.get(nums[i])+1);
            }else {
                map.put(nums[i],1);
            }
        }
        for (Integer key:map.keySet()) {
            if(map.get(key)>nums.length/2){
                return key;
            }
        }
        return 0;
    }

    //如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 n/2向下取整 的元素（下标从 0 开始）一定是众数。
    public int method2(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }

    // 方法三：随机化
    // 思路
    // 因为超过  n/2向下取整的数组下标被众数占据了，这样我们随机挑选一个下标对应的元素并验证，有很大的概率能找到众数。

    //方法四
    //如果一个数组有大于一半的数相同，那么任意删去两个不同的数字，新数组还是会有相同的性质。
    public int method4(int[] nums) {
      int candidate=nums[0],count=1;
        for (int i = 1; i < nums.length; i++) {
            if(count==0){
                candidate=nums[i];
                count++;
                continue;
            }
            if(candidate==nums[i]){
                count++;
            }else{
                count--;
            }
        }
        return candidate;
    }

    public int practice(int[]nums){
        int count=1;
        int more=nums[0];
        for (int i = 1; i < nums.length; i++) {
            if(count==0){
                more=nums[i];
                count++;
            }else{
                if(nums[i]==more){
                    count++;
                }else {
                    count--;
                }
            }
        }
        return more;
    }

    public int practice2(int[]nums){
        int count=0;
        int num=nums[0];
        for (int i = 1; i < nums.length; i++) {
            if(count==0){
                num=nums[i];
                count=1;
            }else{
                if(nums[i]!=num){
                    count--;
                }else{
                    count++;
                }
            }
        }
        return num;
    }
}
